package com.leetcode.partition2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/25 10:03
 */
public class LC120三角形最小路径和 {

    public static int minimumTotal(List<List<Integer>> triangle) {
        return dynamicProgramming(triangle);
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));
        System.out.println(minimumTotal(triangle));
    }

    private static int dynamicProgramming(List<List<Integer>> triangle) {
        int answer = Integer.MAX_VALUE;
        int[][] dp = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
        for (int j = 0; j < triangle.get(0).size(); j++) dp[0][j] = triangle.get(0).get(j);     //初始化第一行
        for (int i = 1; i < triangle.size(); i++) dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0); //初始化第一列

        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 1; j < triangle.get(i).size(); j++) {
                //当前路径最小值只能来源于上一行或者左上行
                if (j == i) dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                else dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
            }
        }
        for (int j = 0; j < triangle.get(triangle.size() - 1).size(); j++) {
            answer = Math.min(answer, dp[dp.length - 1][j]);
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return answer;
    }
}
